#ifndef GRAPH_TOOLS_H_INCLUDED
#define GRAPH_TOOLS_H_INCLUDED

#include <algorithm>
#include <vector>

using namespace std;

ostream& operator << (ostream& o, const vector<size_t>& a)
{
    o << "{";
    for(size_t i  = 0; i < a.size(); ++i) o << a[i] << ",";
    o << "}" << endl;
    return o;
}

inline size_t maxDegree(IGraph& g)
{
    size_t ans = 0;
    for(size_t i = 0; i < g.numVertecies(); ++i) {
        ans = max(ans, g.degree(i));
    }
    return ans;
}

inline size_t subset(size_t v, vector<size_t>& taken, const vector<vector<bool> >& g)
{
    size_t ans = taken.size();
    //cout << taken;
    if (v < g.size()) {
        ans = max(ans, subset(v + 1, taken, g));
        bool ok = true;
        for(size_t i = 0; i < taken.size(); ++i) {
            if (g[taken[i]][v]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            taken.push_back(v);
            ans = max(ans, subset(v + 1, taken, g));
            taken.pop_back();
        }
    }
    return ans;
}

inline size_t solveThis(const vector<size_t>& inc, IGraph& g)
{
    //cout << "@# " << inc;
    vector<int> d(inc.size());
    int n = 0;
    for(size_t i = 0; i < inc.size(); ++i) {
        for(size_t j = 0; j < inc.size(); ++j) {
            if (g.isConnected(inc[i], inc[j])) d[i]++;
        }
        if (d[i]) ++n;// else cout << "!@ " << inc[i] << endl;
    }
    vector<vector<bool> > gr(n, vector<bool>(n,false));
    int vi = 0;
    for(size_t i = 0; i < inc.size(); ++i) if (d[i] > 0) {
        int vj = 0;
        for(size_t j = 0; j < inc.size(); ++j) if (d[j] > 0) {
            gr[vi][vj] = g.isConnected(inc[i], inc[j]);
            ++vj;
        }
        ++vi;
    }
    vector<size_t> taken;
    taken.reserve(gr.size());
    return subset(0, taken, gr) + inc.size() - n;
}

inline size_t maxDegreeHitr(IGraph& g, IGraph& notG)
{
    size_t ans = 0;
    for(size_t t = 0; t < g.numVertecies(); ++t) {
        const vector<size_t>& inc = g.incendents(t);
        size_t forOne = solveThis(inc, notG);
        ans = max(ans, forOne);
        //cout << t << " " << ans << endl;
    }
    return ans;
}

inline size_t numDegreeHitrSmall(IGraph& g, IGraph& notG)
{
    size_t ans = 0;
    for(size_t t = 0; t < g.numVertecies(); ++t) {
        const vector<size_t>& inc = g.incendents(t);
        size_t forOne = solveThis(inc, notG);
        if (forOne <= n) ++ans;
    }
    return ans;
}

#endif//GRAPH_TOOLS_H_INCLUDED
